Computers store files on storage devices such as disk drives. The disk drive only provides a place to store data, similar to an empty file cabinet. Just as an empty filing cabinet does not come with any predefined filing system for files (i.e., users of the filing cabinet must create the filing system or organizational structure themselves, e.g., by alphabetizing files), a hard drive is also, by default, just an empty storage space. By itself, the only way to access data on a hard drive is by either specifying the data's physical location (e.g., by specifying the cylinder, head, and sector of the hard drive where a file is stored), or by its logical location (e.g., the 21,671st block) on the disk. Once the hard disk drive is installed on a computer, the computer uses a file system to keep track of files stored on the hard disk drive in an easily-accessible manner.
Known file systems unduly limit how the operating system and user of the file system can organize files in the file system. That is, known file systems typically require users to organize items in a tree of files and directories, where directories are in fact a special kind of file identified by the file system. Even if a file system supports additional data structures, this capability is typically not exposed to the file system's clients (i.e., end-users and applications). FIG. 2 illustrates a brief example of a typical organizational structure 201 of present file systems. As illustrated in FIG. 2, known file systems use a tree to organize directories (illustrated with rounded ends) and files (illustrated with squared off ends). In a tree structure, an item's location and organization are conflated; every item must be in one and in exactly one directory. This is how the user must organize his or her files, and the user is unable to place an item in multiple organizations without creating a new copy of the item.
Typical file systems use two tables or databases in conjunction with each other to organize files. The first table or database is a lookup table that identifies the physical location at which a file is stored on a storage device such as a hard drive. The second table defines the organizational structure of the files. These tables are generically referred to herein as the location table (LOC) and organizational table (ORG), respectively. The organizational table stores information regarding holding links, i.e., that one item is the parent of another item. Some file systems may combine the location table and the organizational table into a single table or structure, but still require that elements of both tables be present in order for the file system to operate properly. For example, in the NT brand file system marketed by Microsoft Corporation, or NTFS, a Master File Table acts as both the location table and as the organizational table. Similarly, the Unix file system, UFS, uses a table of i-nodes that acts as both the location table and the organizational table for files. Directories are stored as a special kind of file, where the directory “file” stores a list of filenames within the directory and their respective i-nodes.
In these and other known file systems, the file system keeps a file stored on the physical storage device as long as the file is located in at least one location as defined by holding links in the organizational table, i.e., there is at least one holding link pointing to the file. That is, if a holding link for a file is deleted from the organizational table, and there are no more holding links pointing to that file, then the file system removes the file's entry in the location table (regardless of whether the file is physically overwritten on the storage device). The storage device may then use the storage space to write new data. For example, if a user were to “delete” the file C:\PROGRAMS\MICROSOFT\OFFICE\WORD\FILE.DOC depicted in FIG. 2, the file system first removes the file's entry from the organizational table. If the file has no other entries in the location table, i.e., the file is not also stored somewhere else, then the file system removes the file's entry in the location table, thus freeing the space for other data. Typically, the file system maintains a reference count of the number of ancestors (called “holding links”) any given item has. When the last holding link on an item is removed, the item is “deleted” By removing the file's reference in the location table. However, this is undesirable from an end-user perspective, as it limits the organizational structures that a file system can use.
Due to the above restrictions and limitations (e.g., deletion as a by-product of removing a file from the tree), file systems do not allow clients to organize data in data structures other than tree-like hierarchies of directories and files. Users want to be able to organize and de-organize items, in a variety of organizational data structures, without concern that a given item will be deleted. It would be an advancement in the art if the lifetime of an item were separate from its organization in the file system. That is, it would be an advancement to provide a file system that does not conflate item lifetime with organizational structure, where an act of organizing or de-organizing the item does not affect its lifetime. Thus, it would be an advancement in the art to provide a file system that does not limit the types of data structures in which the operating system and/or user can organize files, and also that does not delete a file simply because it is removed from all organizational structures within the file system or has no holding links pointing to the file.